package algorithms.leaning.class15;

import common.util.MyUtil;

/**
 * leetcode 200
 * <p>
 * 给定一个二维数组matrix，里面的值不是1就是0，
 * 上、下、左、右相邻的1认为是一片岛，
 * 返回matrix中岛的数量
 *
 * @author guichang
 * @date 2021/6/14
 */

@SuppressWarnings("all")
public class Code2_并查集_岛问题 {

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 1, 1, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 1, 1},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0},
        };
        MyUtil.print(islandNum(matrix));
    }

    public static int islandNum(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1) {
                    infect(matrix, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private static void infect(int[][] matrix, int i, int j) {
        // 边界判断
        if (i >= matrix.length || j >= matrix[0].length || i < 0 || j < 0) {
            return;
        }
        if (matrix[i][j] == 1) {
            matrix[i][j] = 0;
            infect(matrix, i - 1, j); // 感染上
            infect(matrix, i + 1, j); // 感染下
            infect(matrix, i, j - 1); // 感染左
            infect(matrix, i, j + 1); // 感染右
        }
    }
}